package com.atguigu.main.sort;

import java.util.Arrays;

/**
 * @author ：剧情再美终是戏
 * @description：归并排序
 * @mail : 13286520398@163.com
 * @date ：Created in 2020/2/29 9:29
 * @modified By：
 * @version: 1.0$
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {1, 4, 3, 2};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    // 1 4 3 2
    // l=0, r=3
    private static void mergeSort(int[] arr, int l, int r) {
        if (l < r) {
            int p = (l + r) / 2;
            mergeSort(arr, l, p);
            mergeSort(arr, p + 1, r);
            merge(arr, p, l, r);
        }
    }

    // 1 4 3 2
    private static void merge(int[] arr, int p, int l, int r) {
        // 创建两个临时数组
        int r1 = p - l + 1;
        int r2 = r - p;
        int[] L = new int[r1 + 1]; // 1 3
        int[] R = new int[r2 + 1]; // 2 4


        // 赋值 L R
        for (int i = 0; i < r1; i++) {
            L[i] = arr[l + i];
        }
        L[r1] = Integer.MAX_VALUE;

        for (int j = 0; j < r2; j++) {
            R[j] = arr[p + j + 1];
        }
        R[r2] = Integer.MAX_VALUE;

        // L R 排序 4, 3, 2, 1
        int i = 0, j = 0;
        for (int k = l; k < r + 1; k++) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i += 1;
            } else {
                arr[k] = R[j];
                j += 1;
            }
        }
    }
}
